CAN（内容寻址网络）

标签

分布式/P2P 与路由

字数

5390 字

阅读时间

21 分钟

CAN（SIGCOMM 2001）是这批四篇里唯一不靠环的一篇。它要回答的问题和同年的 Chord 是同一个 —— 在一个没有目录服务器的、几十万节点的系统里，怎么找到某个 key 存在哪个节点上，但给出的答案完全不同：把哈希表的桶摊到一个 $d$ 维笛卡尔坐标空间里，每个节点领一块坐标区域，路由就是在这个空间里走直线。

当时两条路各自的问题很清楚：

• Napster：文件传输是 P2P 了，但定位文件仍然完全中心化 —— 一个中心服务器存全部文件的索引。这既昂贵（中心目录要扩容），又脆弱（单点故障）。规模锚点：Napster 到 2000 年 12 月已被下载 5000 万次，而单日通过 Napster 广告出来的内容就超过 7 TB。
• Gnutella：连定位也去中心化了，但每个请求靠带范围限制的洪泛，而洪泛显然不 scalable，且因为洪泛必须被截断，可能找不到系统里实际存在的内容。

核心：把哈希表摊进坐标空间

我们的设计围绕一个虚拟的 $d$ 维笛卡尔坐标空间，架在 $d$-环面（$d$-torus）上。这个坐标空间完全是逻辑的，与任何物理坐标系无关。

任意时刻，整个坐标空间被动态划分给系统里所有节点，每个节点拥有自己那块互不重叠的区域（zone）。存取的方式因此退化为几何问题：

• 存 $(K_1,V_1)$：用一个均匀哈希函数把 $K_1$ 确定性地映射到空间中一个点 $P$，$(K_1,V_1)$ 就存拥有包含 $P$ 的那块区域的节点上；
• 取 $K_1$：任何节点施加同一个确定性哈希函数把 $K_1$ 映射到 $P$，然后从 $P$ 处取值。

于是哈希表的功能由坐标空间承担，节点之间只需要维持几何上相邻的关系。

邻居的定义与路由

在 $d$ 维空间里，两个节点是邻居，当且仅当它们的坐标区域在 $d-1$ 个维度上重叠、在一个维度上相接（abut）。 图例很具体：节点 5 与节点 1 相邻，因为它们在 $Y$ 轴上重叠、在 $X$ 轴上相接；而节点 6 与 1 在 $X$ 与 $Y$ 两个方向上都相接，所以不是邻居。

路由就是沿直线走：一条 CAN 消息带上目的坐标，节点用自己那份邻居坐标集合做简单的贪心转发，发给坐标最接近目的地的邻居。这份纯局部的邻居状态足以在空间中任意两点之间路由。

复杂度的对照是全篇最漂亮的一处 —— 它给出了一个明确的、与 $n$ 无关的设计点：

	路径长度	每节点状态
CAN（$d$ 维，$n$ 等分）	$(d/4)n^{1/d}$ 跳	$2d$ 个邻居
同期位置服务类路由算法	$O(\log n)$	$O(\log n)$

脚注里点出了这个联系：如果取 $d=({\log }_{2}n)/2$，CAN 就能达到与那些算法相同的扩展特性。但它选择让 $d$ 与 $n$ 无关地固定，理由写得很清楚：

因为我们设想把 CAN 用于非常大的、拓扑频繁变化的系统。在这类系统里，让邻居数量与系统规模无关是重要的。

这是我在这批材料里见到的最干净的一个"两个 O(log n) 方案为什么不选"的论证 —— 目标函数落在每节点状态的稳定性上，而不是渐近最优。

多条路径的存在带来了容错：空间中两点之间有很多条路，所以即使一个或多个邻居崩溃，节点也能自动沿次优的可用路径走。若某方向上的邻居全丢了、而修复机制还没把空洞补上，贪心转发会临时失败 —— 此时节点可以用 expanding ring search（在 CAN 覆盖网上的无状态、受控洪泛） 找一个比自己更接近目的地的节点，再从这个节点继续贪心。

加入、离开与失败接管

加入分三步：① 找到一个已在 CAN 里的节点；② 靠 CAN 路由找到一个要被切分的节点；③ 通知被切区域的邻居，使路由能包含新节点。切分方式是原节点把自己的区域一分为二，留一半、给新节点一半。

bootstrap 用的是 YOID 那套：CAN 关联一个 DNS 域名，解析到一个或多个 bootstrap 节点的 IP；bootstrap 节点维护一份它认为在线的节点名单，返回若干随机选中的节点的地址。

正常离开是把区域交给一个邻居：若能与该邻居的区域合并成一个合法区域就合并；否则交给当前区域最小的那个邻居，由它临时管两块区域。

失败接管（节点不可达）走的是即时接管算法：正常情况下节点周期性向每个邻居发更新消息（含自己的区域坐标、以及邻居列表及其坐标），邻居长时间没有更新就判其失败。判定后节点启动一个接管定时器，初值与该节点自己区域的体积成正比；超时后向失败节点的所有邻居广播一条 TAKEOVER 消息，带上自己的区域体积；收到 TAKEOVER 的节点如果消息里的体积比自己的小就取消自己的定时器，否则回一条自己的 TAKEOVER。这样选出的接管者既存活、区域体积又小。

一个会被漏掉的边界情形

多个相邻节点同时失败时，可能出现"某节点察觉到失败、但失败节点的邻居里可到达的不到一半"的情况。这种情形下如果直接接管，CAN 状态可能变得不一致。处理方式是先做一次 expanding ring search 找失败区域之外的节点，重建足够的邻居状态后再安全地触发接管。

另外正常离开与即时接管都可能让一个节点持有多个区域。为了防止空间被反复碎片化，有一个后台的区域重分配算法（附录 A）把系统推回"一节点一区域"。

七项设计改进

基础版被称作 "bare bones"，其上有七项设计改进。它的目标函数说得很清楚：CAN 的跳是应用层跳，不是 IP 跳；在 CAN 里相邻的两个节点可能隔着几千英里、几十个 IP 跳。所以

我们的策略是降低路径延迟 —— 要么减少路径长度，要么降低单跳延迟。

一、维度数 $d$

增加维度能减少路径长度，代价是路由表略大。实测路径长度按 $O(d\cdot n^{1/d})$ 变化，与分析结果一致（$d$ 越大 → $n^{1/d}$ 越小）。附带好处是容错也改善，因为可选的下一跳更多。

二、多个"现实"（realities）

$r$ 个 reality 就是 $r$ 个互相独立的坐标空间，每个节点在每个 reality 上被分配一块不同的区域，因此持有 $r$ 份独立邻居集，哈希表的内容在每一个 reality 上都被复制。这一条同时买到两样东西：数据可用性（$(x,y,z)$ 处的指针只在 $r$ 个对应节点同时不可用时才不可用）与路由容错（一个 reality 上的路由断裂时可以用其余的继续路由）。

还有一个不那么显眼的收益：同一个节点在 $r$ 个 reality 上拥有的区域位置彼此不同、可能相距很远，于是单个节点有能力一跳到达坐标空间的遥远部分，从而大幅降低平均路径长度。

维度 vs reality 的取舍，给出的结论很克制：

对相同的邻居数而言，增加空间的维度比增加 reality 数得到更短的路径长度。但不应由此推断"多维度比多 reality 更有价值" —— reality 还带来数据可用性与容错。真正该带走的一点是：如果愿意为了提升路由效率而增加每节点邻居状态，那么正确的做法是增加坐标空间的维度 $d$，而不是 reality 的数量 $r$。

三、RTT 加权的路由度量

基础度量是笛卡尔距离上的进展。改进方式是每个节点测量到各邻居的网络层 RTT，转发时发给"进展 / RTT 之比最大"的邻居。它瞄准的是降低单跳延迟而不是缩短路径长度，所以评估指标是单跳延迟（端到端延迟 ÷ 路径长度）。

在 100ms（transit 内）/ 10ms（stub-transit）/ 1ms（stub 内）的 Transit-Stub 拓扑上、底层 IP 路径平均端到端延迟约 115 ms：

维度 $d$	不加权（ms）	RTT 加权（ms）
2	116.8	88.3
3	116.7	76.1
4	115.8	71.2
5	115.4	70.9

不加权时单跳延迟与底层平均 IP 延迟基本持平；加权后单跳延迟降低 24% 到 40%，且维度越高改善越大（下一跳选择更多）。

四、区域超载（zone overloading）

允许多个节点共享同一块区域，共享者称为 peer，系统参数 MAXPEERS 限其上界（实际取值设想得很低，比如 3 或 4）。节点只需在相邻区域里各选一个代表作为邻居，所以超载不会增加邻居信息量，只多出一份最多 MAXPEERS 的 peer 状态。

新节点加入时，若目标区域里的 peer 还没满就直接入伙、不切分空间；满了才按老办法一分为二，并用**一个确定性规则（例如按 IP 地址排序）**把 peer 加新节点在切成两半后均分。

超载买到三样：

• 路径长度下降 —— 每区域放多个节点与"减少系统里的节点数"效果等价；
• 单跳延迟下降 —— 邻居有多个候选，可以挑延迟更近的（节点会向邻居索取 peer 列表、测量到该区域内所有节点的 RTT、保留最低的那个）；
• 容错改善 —— 一块区域只有在其中所有节点同时崩溃时才空置。

每区域节点数	单跳延迟（ms）
1	116.4
2	92.8
3	72.9
4	64.4

每区域放 4 个节点可把单跳延迟降低约 45%。 代价是复杂度 —— 节点要多维护一份 peer 集合。区域内数据的处理则是一个二选一：复制换更高可用性但每节点数据量乘上 MAXPEERS、且需要一致性机制；划分不需要一致性机制也不增加存储，但也不提升可用性。

五、多个哈希函数

用 $k$ 个不同哈希函数把同一个 key 映射到空间里 $k$ 个点，从而把一份 $(K,V)$ 复制到 $k$ 个不同节点上 —— 于是它只在 $k$ 个副本同时不可用时才不可用。并且查询可以并行发给这 $k$ 个节点，从而降低平均查询延迟。代价是数据库体积与查询流量乘 $k$。另有一个折中：不查全部 $k$ 个，而是从坐标上离自己最近的那个取。

六、landmark 加权的覆盖网构造

基础构造把节点随机分配到区域，于是邻居在底层 IP 拓扑上不一定近 —— 典型例子是一个 Berkeley 的 CAN 节点可能邻居在欧洲，于是它到附近 Stanford 的路径会绕道欧洲。

做法是借一组众所周知的机器（例如 DNS 根域名服务器）当 landmark：每个节点测到各 landmark 的 RTT 并把 landmark 按 RTT 升序排，于是有 $m$ 个 landmark 就有 $m!$ 种可能的序；把坐标空间切成 $m!$ 等份，每份对应一种序；新节点改用"在与自己序对应的那份空间里随机取点"来加入。理由是拓扑上接近的节点很可能有相同的序，于是落在同一份空间里，从而坐标上的邻居很可能在 Internet 上也近。

评估指标是 latency stretch —— CAN 网络延迟与 IP 网络平均延迟之比。

这一项在最终的总体评测里是 OFF（表 4/5），只有这里的单项实验给了数据。

另外它带来一个副作用：坐标空间不再均匀填充 —— 有些序（桶）出现的概率更高，对应空间更拥挤，造成负载略不均匀，需要用后台的负载均衡把空间从过载节点匀给轻载节点。

七、更均匀的划分

新节点加入时发往某随机点的属主，而该属主不仅知道自己的区域坐标，也知道邻居的。所以它先把自己的区域体积与直接邻居的比较，切分体积最大的那个，而不是无脑切自己。

这条能当负载均衡用的理由是：因为 $(K,V)$ 是用均匀哈希散开的，节点区域的体积就指示了它要存多少数据、也就指示了它承受的负载。这条的不足也很明确：这不构成真正的负载均衡，因为有些 $(K,V)$ 就是比别的更热，会把负载压在持有它们的节点上。

实测效果（$2^{16}$ 个节点）：不使用该特性时，约 40% 刚出头的节点拿到体积为 $V$（即 $V_T/n$）的区域；使用后接近 90%；最大区域体积从 $8V$ 降到 $2V$。

热点：缓存与副本

某些 $(K,V)$ 会被远比其他频繁访问，所以借用了 Web 上那套手法：

• 缓存：节点除主数据外，缓存它最近访问过的 key；转发请求前先查自己的缓存，命中就自己应答。于是一个 key 能由多少份缓存来服务，与它的热度成正比 —— 请求这个 key 的行为本身就让它更广泛可用；
• 复制：发现自己被某一个 key 的请求压垮的节点，把该 key 复制到它的每个邻居上。复制是主动把热门 key 推出去，而缓存是请求 key 的自然结果；热门 key 最终会在原存储节点周围形成一个区域内的副本。持有副本的节点可以按一定概率选择自己应答或继续转发，从而让负载散布在整个区域而不只是外围。

两者都需要 TTL、并最终过期。

总体评测

"bare bones" 与 "knobs-on-full" 两个配置在 $n=2^{18}$（26 万多个节点）上做累计效果对照：

参数	bare bones	knobs-on-full
维度 $d$	2	10
reality 数 $r$	1	1
每区域 peer 数 $p$	0	4
哈希函数数 $k$	1	1
RTT 加权度量	OFF	ON
均匀划分	OFF	ON
landmark 排序	OFF	OFF

指标	bare bones	knobs-on-full
路径长度	198.0 跳	5.0 跳
邻居数	4.57	27.1
peer 数	0	2.95
IP 延迟	115.9 ms	82.4 ms
CAN 路径延迟	23,008 ms	135.29 ms

三条关键读数：对 26 万节点以上的系统，我们能以"与底层网络延迟之比远在两倍以内"的延迟完成路由；为此每节点要维护约 30 个邻居（27.1 + 2.95），这"偏高但不至于不合理"；最大的收益来自增加维度 —— 它把路径长度从 198 降到约 5 跳，但延迟启发式也很重要：没有它们，端到端延迟会接近 $5\times 115$ ms。

关于 82.4 ms 这个比底层 115 ms 还小的数，脚注澄清了这一点：原因与物理网络平均延迟无关：用了区域超载与 RTT 加权后，CAN 会自动从最近的副本取数据 —— 82 ms 是取数节点到这个最近副本的网络层平均延迟。

规模外推：路径长度随 $n$ 增长得很慢（$2^{14}$ 时 4.56 跳，$2^{18}$ 时 5.0 跳），且新增的跳落在网络边缘的低延迟链路上，所以总路径延迟增长甚至比 $n^{1/10}$ 更慢。若做悲观假设（假设延迟随路径长度按 $n^{1/10}$ 增长）后外推：在路径延迟恶化到"底层网络延迟四倍以内"之前，系统规模还能再扩 $2^{10}$，接近十亿节点。

延迟 stretch 对链路延迟分布的敏感性（四种拓扑：$H(100,10,1)$、$H(20,5,2)$、$R(10,50)$、$10\times H(20,5,2)$）：在 13 万节点以内的所有情形下，latency stretch 都没有超过 3；随机延迟分布下增长最快（因为此时边缘新增的链路不必然是低延迟链路）；$H(20,5,2)$ 略优于 $10\times H(20,5,2)$，因为前者节点密度更高、延迟启发式收益更大。

与 Plaxton 算法的位置

Plaxton 算法是当时最近的同类方案，但最终没被采用：每个节点有一个 $n$ 位标签，分成 $l$ 层、每层 $w=n/l$ 位；标签为 $xyz$ 的节点持有三类路由表（形式为 $\ast XX$、$x\ast X$、$xy\ast$ 各 $2^w$ 项）；转发时从左到右逐位"求解"目的标签，每次交给"比自己在左边多匹配一位"的邻居。

对照：Plaxton 路由 $O(\log n)$ 跳、路由表 $O(\log n)$；CAN 路由 $O(d{n}^{1/d})$ 跳、路由表 $O(dr)$ 且与 $n$ 无关。 取 $d=({\log }_{2}n)/2$ 时 CAN 同样能匹配 Plaxton 的扩展特性，而且一开始确实认真考虑过用它。至于为什么最终没选 Plaxton（以及为什么不用 DV / LS 这类 IP 路由算法、也不用传统层次路由），理由都指向同一个取向：DV/LS 需要广泛传播本地拓扑信息，适合拓扑变化不频繁的 IP 网络，而 CAN 面向的是"大量可能不稳定的节点"；层次路由会压在一小撮节点上、且有单点故障。CAN 要的是真正分布式的路由算法。

相关

• Chord —— 同年（SIGCOMM 2001）的另一条路：Chord 把节点排在环上、用 finger table 做 $O(\log n)$ 路由，每节点状态也是 $O(\log n)$；CAN 反过来放弃对数级、换"状态数与 $n$ 无关"。这两篇的对照就是"渐近最优"与"状态稳定性"的取舍
• 一致性哈希算法 —— 两者都靠哈希把 key 摊到节点上，但一致性哈希要的是"节点增减时少搬数据"，CAN 要的是"路由不需要目录"；一致性哈希用环 + 虚拟节点处理倾斜，CAN 用区域切分 + 均匀划分 + 区域超载处理
• Ceph —— CRUSH 与 CAN 都属于"位置算得出来"，但 CAN 是节点自己组织出一个坐标空间（邻居靠几何关系），CRUSH 是用分层 cluster map + 规则做纯函数映射，不需要节点间维持邻居关系
• Dynamo —— 同属"没有中心目录"的一族；Dynamo 用一致性哈希环 + 虚拟节点，且节点之间靠 gossip 传播成员关系，而 CAN 靠周期性邻居更新消息 + 接管定时器

参考

• S. Ratnasamy, P. Francis, M. Handley, R. Karp, S. Shenker. A Scalable Content-Addressable Network. SIGCOMM 2001.
• C. G. Plaxton, R. Rajaraman, A. W. Richa. Accessing Nearby Copies of Replicated Objects in a Distributed Environment. SPAA 1997.

贡献者

YJ

文件历史

最后编辑于 2 天前查看完整历史

ae1ee-docs：内容完善

448f1-分布式